#ifndef CARTESIAN_TREE_HPP
#define CARTESIAN_TREE_HPP
#include "entry.hpp"
#include "list.hpp"
using namespace poly;

struct CTe {
	int x,y,c,ix;
	entry data;
	CTe *l,*r;
	inline CTe(entry obj);
	void gen_list(list<entry> &l);
	void clear();
};

struct CT {
	CTe *tree;
	CT();
	void ins(entry obj);
	void del(entry obj);
	void gen_list(list<entry> &l);
	void clear();
	bool isempty();
};
inline void norm(CTe *t);
void split(CTe *&l,CTe *&r,CTe *t,int k);
void spliti(CTe *&l,CTe *&r,CTe *t,int k);
void merge(CTe *l,CTe *r,CTe *&t);
int find(CTe *t);

#endif
